package com.zhanghp.class035;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

/**
 * 插入、删除和获取随机元素O(1)时间的结构
 * <br/>
 * 测试链接 : https://leetcode.cn/problems/insert-delete-getrandom-o1/
 *
 * @author zhanghp
 * @since 2024/4/13 16:57
 */
public class Code03_InsertDeleteRandom {

    public static void main(String[] args) {
        RandomizedSet randomizedSet = new RandomizedSet();
        randomizedSet.insert(1);
        randomizedSet.insert(2);
        randomizedSet.remove(2);
        randomizedSet.getRandom();
    }

    static class RandomizedSet {

        /**
         * key : 传入的值<br/>
         * val : arr的长度
         */
        public Map<Integer, Integer> map;

        public ArrayList<Integer> arr;


        public RandomizedSet() {
            arr = new ArrayList<>();
            map = new HashMap<>();
        }

        public boolean insert(int val) {
            if (map.containsKey(val)) {
                return false;
            }
            map.put(val, arr.size());
            arr.add(val);
            return true;
        }

        public boolean remove(int val) {
            if (!map.containsKey(val)) {
                return false;
            }
            // 因为删除一个元素，那么arr需要把此节点的索引替换掉，替换为arr最后一个尾节点的值
            // 如果删除的是最后一个节点怎么办
            // 如果删除最后一个节点，因为先set，后remove，set时的索引就是最后一个索引，而remove也是最后一个索引，所以不会有问题，map同理
            // set,remove 要依次进行
            Integer curIndex = map.get(val);
            Integer endValue = arr.get(arr.size() - 1);
            arr.set(curIndex, endValue);
            arr.remove(arr.size() - 1);

            // 开始处理map
            map.put(endValue, curIndex);
            map.remove(val);
            return true;
        }

        public int getRandom() {
            return arr.get((int)(Math.random() * arr.size()));
        }
    }
}
